package mygraph;

import java.util.Stack;

public class DFS_Vertex {
	class Vertex {
		private char lable;
		private int val;
		private boolean wasvisited;
		Vertex(char lable) {
			this.lable = lable;
		}
		Vertex() {
			
		}
	}
	private char lable; // 矩阵元素
	private Vertex[][] list = new Vertex[20][20];
	private Vertex[] vertexList = new Vertex[20];
	private int nVerts; // 当前顶点下标
	DFS_Vertex() {
		this.nVerts = 0;
		for(int i = 0; i < 20; i ++) {
			for(int j = 0; j < 20; j ++) {
				list[i][j] = new Vertex();
			}
		}
	}

	// 增加一个顶点
	public void addVertex(char lable) {
		vertexList[nVerts++] = new Vertex(lable);
	}

	// 增加一条边
	public void addEdge(int start, int end) {
		list[start][end].val = 1;
		list[end][start].val = 1;
	}

	// 打印矩阵
	public void printMatrix() {
		for (int i = 0; i < nVerts; i++) {
			for (int j = 0; j < nVerts; j++) {
				System.out.print(list[i][j].val);
			}
			System.out.println();
		}
	}
	//显示字符
	public void showVertex(int v) {
		System.out.print(vertexList[v].lable + "\t");
	}
	//获得邻接未访问节点
	public int getAdjUnvisitedVertex(int v) {
		for(int j = 0; j < nVerts; j ++) {
			if((list[v][j].val == 1) && (vertexList[j].wasvisited == false)) {
				return j;
			}
		}
		return -1;
	}
	//DFS
	public void DFS() {
		Stack<Integer> s = new Stack();
		vertexList[0].wasvisited = true;
		showVertex(0);
		s.push(0);
		int v;
		while(s.size() > 0) {
			v = getAdjUnvisitedVertex(s.peek());
			if(v == -1) {
				s.pop();
			}else {
				vertexList[v].wasvisited = true;
				showVertex(v);
				s.push(v);
			}
		}
		for(int j = 0; j < nVerts; j ++) {
			vertexList[j].wasvisited = false;
		}
	}
	public static void main(String[] args) {
		DFS_Vertex ds = new DFS_Vertex();
		ds.addVertex('A');	//0
		ds.addVertex('B');	//1
		ds.addVertex('C');	//2	
		ds.addVertex('D');	//3
		ds.addVertex('E');	//4
		ds.addEdge(0, 1);	//A-B 
		ds.addEdge(0, 3);	//A-D
		ds.addEdge(1, 4);	//B-E
		ds.addEdge(3, 4);	//D-E
		ds.addEdge(4, 2);	//E-C
		ds.printMatrix();
		ds.DFS();
	}
}
